package com.mc.sort;

import com.mc.general.Tools;

public class HeapSort {
	public static <T extends Comparable<T>> void sort(T[] array){
		int n = array.length;
		for(int k=n/2-1;k>=0;k--){//构造有序堆
			sink(array,k,n);
		}
		while(n>0){//排序
			Tools.exchange(0, --n, array);
			sink(array,0,n);
		}
	}
	//下沉操作
	private static <T extends Comparable<T>> void sink(T[] array, int k,int n){
		while(2*k+1<=n-1){//循环条件用来保证左孩子的存在
			int j=2*k+1;
			if(j<n-1&&Tools.compare(array[j], array[j+1])==-1)j++;//第一个条件用来保证右孩子的存在
			if(Tools.compare(array[k], array[j])==1)break;
			Tools.exchange(k, j, array);
			k=j;//切换当前节点
		}
	}
	//上浮操作
	private static <T extends Comparable<T>> void swim(T[] array,int k, int n){
		while(k>1){
			int j = k/2;
			if(Tools.compare(array[k], array[j])==1)
				Tools.exchange(k, j, array);
			k=j;
		}
	}
}
